NTT残疾人手册

建议先阅读FFT的残疾人手册

0.简介

首先fft的计算方式是在实数域下进行运算的

所以难免会有精度误差，但是如果我们需要在模的意义下快速求多项式的卷积FFT就失灵了

因此NTT就出现了

1.原根的介绍

关于单位根的性质回顾

我们需要一个在模意义下成立的具有单位根性质的东西

那么单位根的性质我们用到了哪一些呢？

$$\omega_n^0\not= \omega_n^1\not= \cdots\not= \omega_n^{n-1}$$ $$\omega_{n}^k=\omega_{\frac{n}{2}}^{\frac{k}{2}}$$ $$\omega_{n}^k=\omega_{n}^{k \% n}$$ $$\omega_{n}^{k+\frac{n}{2}}=-\omega_{n}^k$$ $$\sum_{k=0}^{n-1} (\omega_n^{j-i})^k = n[i=j]$$

原根概念的引入

模数Mod的原根g的定义是需要满足：

$$g^0\not= g^1\not= \cdots\not= g^{p-2} \pmod {Mod}$$

而模数Mod定要满足是质数且可以表示成$Mod = k\cdot2^r+1$的形式

在这种情况下令$g_n=g^k\pmod {Mod}$

就可以使得：

$$g_n^0\not= g_n^1\not= \cdots\not= g_n^{n-1} \pmod {Mod}$$

这样的话，我们就可以用原根来代替单位根进行模意义下的快速变换了

主要过程和fft没有本质区别